package com.hainiu.cat.sort.write;

/**
 * create by biji.zhao on 2021/5/30
 */
public class ReverseSingleLinked {

    private static class LinkNode {
        private int data;
        private LinkNode next;

        public LinkNode getNext() {
            return next;
        }

        public void setNext(LinkNode next) {
            this.next = next;
        }

        public LinkNode(int data) {
            this.data = data;
        }
    }

    private static LinkNode digui(LinkNode e) {
        if (e == null || e.getNext() == null) {
            return e;
        }
        LinkNode rehead = digui(e);
        e.getNext().setNext(e);
        e.setNext(null);
        return rehead;
    }

    // 单链表反转
    private static LinkNode cover(LinkNode e) {
        // 新头
        LinkNode reHead = null;
        // next
        LinkNode next;
        while (e != null) {
            next = e.getNext();
            e.setNext(reHead);
            // 当前节点就是reHead
            reHead = e;
            e = next;
        }
        return reHead;
    }

    public static void main(String[] args) {
        LinkNode a = new LinkNode(100);
        LinkNode b = new LinkNode(200);
        a.setNext(b);

        LinkNode c = new LinkNode(300);
        b.setNext(c);

        LinkNode d = new LinkNode(400);
        c.setNext(d);

        printLinkList(a);
//        a = recursionReverse(a);
        a = loopReverse(a);
        printLinkList(a);
    }

    private static void printLinkList(LinkNode e) {
        StringBuilder builder = new StringBuilder();
        LinkNode i = e;
        builder.append("_").append(i.data);
        while (i.getNext() != null) {
            builder.append("-").append(i.getNext().data);
            i = i.getNext();
        }
        System.out.println(builder.toString());
    }

    /**
     * 递归实现反转
     */
    private static LinkNode recursionReverse(LinkNode e) {
        if (e == null || e.getNext() == null) {
            return e;
        }
        // 新头节点
        LinkNode reHead = recursionReverse(e.getNext());
        e.getNext().setNext(e);
        e.setNext(null);
        return reHead;
    }

    private static LinkNode loopReverse(LinkNode e) {
        LinkNode reHead = null;
        LinkNode next;

        while (e != null) {
            next = e.getNext();
            e.setNext(reHead);
            reHead = e;
            e = next;
        }
        // 切记，此处返回 reHead
        return reHead;
    }
}
